In recent years, electronic commerce such as the net banking and the online shopping has been widely used in the Internet. In such electronic commerce, the public key based technology is used to prevent the transactions from being tampered with.
The public key based technology prevents transactions from being tampered with by the structure where an authority called certificate authority issues a certificate (public key certificate) of a public key complying with the public key encryption, to online shopping sites and the like, and the users of the sites use the issued public key certificate. More specifically, the public key based technology prevents spoofing of a site by verifying whether or not the public key certificate has been issued from a reliable certificate authority, and prevents transactions from being tampered with by constructing an encryption transmission path by using the public key. For example, Patent Document 1 identified below discloses an authentication system in which a plurality of devices confirm the reliability thereof with each other by tracing the reliability relationship tree structure.
In such an authentication system, it is necessary to secretly manage a private key corresponding to the public key to prevent the private key from leaking to a malicious third party. This is because if the private key is known to a malicious third party, the malicious third party may spoof the certificate authority and use the private key in an unauthentic manner.
One of technologies for preventing the private key from leaking is managing the private keys by the secret sharing method (Non-Patent Document 1).
According to the secret sharing method, important private information S such as a private key is held in the state of a k pieces of shared information generated from the private information S, where “k” is an integer of 2 or higher. In this case, the original private information S is generated by using the k pieces of shared information. Each piece of shared information is assigned to a different holding device and held by the assigned holding device.
With this structure, even if a piece of shared information is leaked, the private information S is not known. This makes it possible to manage the private information S safely.    Patent Document 1: Japanese Patent Application Publication No. 10-215245    Non-Patent Document 1: Tatsuaki Okamoto and Hirosuke Yamamoto, “Gendai Angou (Modern Encryption)”, Sangyo Tosho Publishing Co., Ltd., 1997    Non-Patent Document 2: ITU-T Recommendation X.509 (1997 E): Information Technology—Open Systems Interconnection—The Directory: Authentication Framework, 1997    Non-Patent Document 3: I. Blake, G. Seroussi and N. Smart, “Elliptic Curves in Cryptography”, CAMBRIDGE UNIVERSITY PRESS, 1999    Non-Patent Document 4: Tatsuaki Okamoto, “Generic conversions for constructing IND-CCA2 public-key encryption in the random oracle model”, [online], The 5th Workshop on Elliptic Curve Cryptography (ECC2001), Oct. 30, 2001, [searched on Feb. 15, 2007], Internet <URL: http://www.cacr.math.uwaterloo.ca/conferences/2001/ecc/okamoto.ppt>    Non-Patent Document 5: D. Boneh, M. Franklin, “Efficient Generation of Shared RSA Keys”, Journal of the ACM, Vol. 48, No. 4, pp. 702-722